home *** CD-ROM | disk | FTP | other *** search
/ Shareware Super Platinum 8 / Shareware Super Platinum 8.iso / mac / PROGTOOL / GZIP107S.ZIP;1 / GZIP107.TAR / gzip-1.0.7 / match.S < prev    next >
Encoding:
Text File  |  1993-03-18  |  11.4 KB  |  378 lines
  1. /* match.s -- optional optimized asm version of longest match in deflate.c
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  *
  6.  * The 68020 version has been written by Francesco Potorti` <pot@cnuce.cnr.it>
  7.  * adapted to the 68000 by Carsten Steger <stegerc@informatik.tu-muenchen.de>
  8.  * and Andreas Schwab <schwab@lamothe.informatik.uni-dortmund.de>.
  9.  */
  10.  
  11. /* $Id: match.S,v 0.12 1993/03/18 18:14:56 jloup Exp $ */
  12.  
  13. /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
  14.  * external symbols with an underline character '_'.
  15.  */
  16. #ifdef NO_UNDERLINE
  17. #  define _prev             prev
  18. #  define _window           window
  19. #  define _match_start        match_start
  20. #  define _prev_length        prev_length
  21. #  define _good_match        good_match
  22. #  define _nice_match        nice_match
  23. #  define _strstart        strstart
  24. #  define _max_chain_length max_chain_length
  25.  
  26. #  define _match_init       match_init
  27. #  define _longest_match    longest_match
  28. #endif
  29.  
  30. #ifdef DYN_ALLOC
  31.   error: DYN_ALLOC not yet supported in match.s
  32. #endif
  33.  
  34. #if defined(i386) || defined(_I386)
  35.  
  36. /* This version is for 386 Unix or OS/2 in 32 bit mode.
  37.  * Warning: it uses the AT&T syntax: mov source,dest
  38.  * This file is only optional. If you want to force the C version,
  39.  * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
  40.  * If you have reduced WSIZE in gzip.h, then change its value below.
  41.  * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
  42.  */
  43.  
  44.     .file   "match.S"
  45.  
  46. #define MAX_MATCH     258
  47. #define MAX_MATCH2      128     /* MAX_MATCH/2-1 */
  48. #define MIN_MATCH    3
  49. #define WSIZE         32768
  50. #define MAX_DIST     WSIZE - MAX_MATCH - MIN_MATCH - 1
  51.  
  52.     .globl    _match_init
  53.     .globl  _longest_match
  54.  
  55.     .text
  56.  
  57. _match_init:
  58.     ret
  59.  
  60. /*-----------------------------------------------------------------------
  61.  * Set match_start to the longest match starting at the given string and
  62.  * return its length. Matches shorter or equal to prev_length are discarded,
  63.  * in which case the result is equal to prev_length and match_start is
  64.  * garbage.
  65.  * IN assertions: cur_match is the head of the hash chain for the current
  66.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  67.  */
  68.  
  69. _longest_match:    /* int longest_match(cur_match) */
  70.  
  71. #define cur_match   20(%esp)
  72.      /* return address */               /* esp+16 */
  73.         push    %ebp                    /* esp+12 */
  74.         push    %edi                    /* esp+8  */
  75.     push    %esi                    /* esp+4  */
  76.     push    %ebx            /* esp    */
  77.  
  78. /*
  79.  *      match        equ esi
  80.  *      scan         equ edi
  81.  *      chain_length equ ebp
  82.  *      best_len     equ ebx
  83.  *      limit        equ edx
  84.  */
  85.     mov     cur_match,%esi
  86.         mov     _max_chain_length,%ebp /* chain_length = max_chain_length */
  87.     mov     _strstart,%edi
  88.     mov     %edi,%edx
  89.     sub    $ MAX_DIST,%edx        /* limit = strstart-MAX_DIST */
  90.     jae    limit_ok
  91.     sub    %edx,%edx              /* limit = NIL */
  92. limit_ok:
  93.         add    $ _window+2,%edi       /* edi = offset(window+strstart+2) */
  94.         mov    _prev_length,%ebx      /* best_len = prev_length */
  95.         movw     -3(%ebx,%edi),%ax      /* ax = scan[best_len-1..best_len] */
  96.         movw     -2(%edi),%cx           /* cx = scan[0..1] */
  97.     cmp    _good_match,%ebx       /* do we have a good match already? */
  98.         jb      do_scan
  99.     shr     $2,%ebp                /* chain_length >>= 2 */
  100.         jmp     do_scan
  101.  
  102.         .align  4
  103. long_loop:
  104. /* at this point, edi == scan+2, esi == cur_match */
  105.         movw    -3(%ebx,%edi),%ax       /* ax = scan[best_len-1..best_len] */
  106.         movw     -2(%edi),%cx           /* cx = scan[0..1] */
  107. short_loop:
  108. /*
  109.  * at this point, di == scan+2, si == cur_match,
  110.  * ax = scan[best_len-1..best_len] and cx = scan[0..1]
  111.  */
  112.         and     $ WSIZE-1, %esi
  113.         movw    _prev(%esi,%esi),%si    /* cur_match = prev[cur_match] */
  114.                                         /* top word of esi is still 0 */
  115.         cmp     %edx,%esi        /* cur_match <= limit ? */
  116.         jbe     the_end
  117.         dec     %ebp                    /* --chain_length */
  118.         jz      the_end
  119. do_scan:
  120.         cmpw    _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
  121.         jne     short_loop
  122.         cmpw    _window(%esi),%cx       /* check min_match_length match */
  123.         jne     short_loop
  124.  
  125.         lea     _window+2(%esi),%esi    /* si = match */
  126.         mov     %edi,%eax               /* ax = scan+2 */
  127.         mov     $ MAX_MATCH2,%ecx       /* scan for at most MAX_MATCH bytes */
  128.         rep;    cmpsw                   /* loop until mismatch */
  129.         je      maxmatch                /* match of length MAX_MATCH? */
  130. mismatch:
  131.         movb    -2(%edi),%cl        /* mismatch on first or second byte? */
  132.         subb    -2(%esi),%cl        /* cl = 0 if first bytes equal */
  133.         xchg    %edi,%eax           /* edi = scan+2, eax = end of scan */
  134.         sub     %edi,%eax           /* eax = len */
  135.     sub    %eax,%esi           /* esi = cur_match + 2 + offset(window) */
  136.     sub    $ _window+2,%esi    /* esi = cur_match */
  137.         subb    $1,%cl              /* set carry if cl == 0 (cannot use DEC) */
  138.         adc     $0,%eax             /* eax = carry ? len+1 : len */
  139.         cmp     %ebx,%eax           /* len > best_len ? */
  140.         jle     long_loop
  141.         mov     %esi,_match_start       /* match_start = cur_match */
  142.         mov     %eax,%ebx               /* ebx = best_len = len */
  143.         cmp     _nice_match,%eax        /* len >= nice_match ? */
  144.         jl      long_loop
  145. the_end:
  146.         mov     %ebx,%eax               /* result = eax = best_len */
  147.     pop     %ebx
  148.         pop     %esi
  149.         pop     %edi
  150.         pop     %ebp
  151.         ret
  152. maxmatch:
  153.         cmpsb
  154.         jmp     mismatch
  155.  
  156. #else
  157.  
  158. /* ======================== 680x0 version ================================= */
  159.  
  160. #if defined(m68k) || defined(__mc68000__) || defined(__MC68000__)
  161. #  ifndef mc68000
  162. #    define mc68000
  163. #  endif
  164. #endif
  165.  
  166. #if (defined(__mc68020__) || defined(__MC68020__)) && !defined(mc68020)
  167. #  define mc68020
  168. #endif
  169.  
  170. #if defined(mc68020) || defined(mc68000)
  171.  
  172. #if defined(mc68020) && !defined(UNALIGNED_OK)
  173. #  define UNALIGNED_OK
  174. #endif
  175.  
  176. #if defined(m68k) && !defined(NeXT) && !defined(atarist)
  177.   /* Try 'delta' style */
  178.  
  179. #  define GLOBAL(symbol)    global    symbol
  180. #  define TEXT            text
  181. #  define FILE(filename)    file    filename
  182. #  define invert_maybe(src,dst)    dst,src
  183. #  define imm(data)        &data
  184. #  define reg(register)        %register
  185.  
  186. #  define addl            add.l
  187. #  define addql            addq.l
  188. #  define blos            blo.b
  189. #  define bhis            bhi.b
  190. #  define bras            bra.b
  191. #  define clrl            clr.l
  192. #  define cmpmb            cmpm.b
  193. #  define cmpw            cmp.w
  194. #  define cmpl            cmp.l
  195. #  define lslw            lsl.w
  196. #  define lsrl            lsr.l
  197. #  define movel            move.l
  198. #  define movew            move.w
  199. #  define moveb            move.b
  200. #  define moveml        movem.l
  201. #  define subl            sub.l
  202. #  define subw            sub.w
  203. #  define subql            subq.l
  204.  
  205. #  define IndBase(bd,An)    (bd,An)
  206. #  define IndBaseNdxl(bd,An,Xn)    (bd,An,Xn.l)
  207. #  define IndBaseNdxw(bd,An,Xn)    (bd,An,Xn.w)
  208. #  define predec(An)        -(An)
  209. #  define postinc(An)        (An)+
  210.  
  211. #else /* Motorola style (Sun 3, NeXT, Amiga, Atari) */
  212.  
  213. #  define GLOBAL(symbol)    .globl    symbol
  214. #  define TEXT            .text
  215. #  define FILE(filename)    .even
  216. #  define invert_maybe(src,dst)    src,dst
  217. #  ifdef sun
  218. #    define imm(data)        #data
  219. #  else
  220. #    define imm(data)        \#data
  221. #  endif
  222. #  define reg(register)        register
  223.  
  224. #  define blos            bcss
  225. #  ifdef sun
  226. #    define movel        movl
  227. #    define movew        movw
  228. #    define moveb        movb
  229. #  endif
  230. #  define IndBase(bd,An)    An@(bd)
  231. #  define IndBaseNdxl(bd,An,Xn)    An@(bd,Xn:l)
  232. #  define IndBaseNdxw(bd,An,Xn)    An@(bd,Xn:w)
  233. #  define predec(An)        An@-
  234. #  define postinc(An)        An@+
  235.  
  236. #endif    /* styles */
  237.  
  238. #define Best_Len    reg(d0)        /* unsigned */
  239. #define Cur_Match    reg(d1)        /* Ipos */
  240. #define Loop_Counter    reg(d2)        /* int */
  241. #define Scan_Start    reg(d3)        /* unsigned short */
  242. #define Scan_End    reg(d4)        /* unsigned short */
  243. #define Limit        reg(d5)        /* IPos */
  244. #define Chain_Length    reg(d6)        /* unsigned */
  245. #define Scan_Test    reg(d7)
  246. #define Scan        reg(a0)        /* *uch */
  247. #define Match        reg(a1)        /* *uch */
  248. #define Prev_Address    reg(a2)        /* *Pos */
  249. #define Scan_Ini    reg(a3)        /* *uch */
  250. #define Match_Ini    reg(a4)        /* *uch */
  251. #define Stack_Pointer    reg(sp)
  252.  
  253. #define MAX_MATCH     258
  254. #define MIN_MATCH    3
  255. #define WSIZE        32768
  256. #define MAX_DIST     (WSIZE - MAX_MATCH - MIN_MATCH - 1)
  257.  
  258.     GLOBAL    (_match_init)
  259.     GLOBAL    (_longest_match)
  260.  
  261.     TEXT
  262.  
  263.     FILE    ("match.S")
  264.  
  265. _match_init:
  266.     rts
  267.  
  268. /*-----------------------------------------------------------------------
  269.  * Set match_start to the longest match starting at the given string and
  270.  * return its length. Matches shorter or equal to prev_length are discarded,
  271.  * in which case the result is equal to prev_length and match_start is
  272.  * garbage.
  273.  * IN assertions: cur_match is the head of the hash chain for the current
  274.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  275.  */
  276.  
  277. /* int longest_match (cur_match) */
  278.  
  279. #ifdef UNALIGNED_OK
  280. #  define pushreg    15928        /* d2-d6/a2-a4 */
  281. #  define popreg    7292
  282. #else
  283. #  define pushreg    16184        /* d2-d7/a2-a4 */
  284. #  define popreg    7420
  285. #endif
  286.  
  287. _longest_match:
  288.     movel    IndBase(4,Stack_Pointer),Cur_Match
  289.     moveml    imm(pushreg),predec(Stack_Pointer)
  290.     movel    _max_chain_length,Chain_Length
  291.     movel    _prev_length,Best_Len
  292.     movel    imm(_prev),Prev_Address
  293.     movel    imm(_window+MIN_MATCH),Match_Ini
  294.     movel    _strstart,Limit
  295.     movel    Match_Ini,Scan_Ini
  296.     addl    Limit,Scan_Ini
  297.     subw    imm(MAX_DIST),Limit
  298.     bhis    L__limit_ok
  299.     clrl    Limit
  300. L__limit_ok:
  301.     cmpl    invert_maybe(_good_match,Best_Len)
  302.     blos    L__length_ok
  303.     lsrl    imm(2),Chain_Length
  304. L__length_ok:
  305.     subql    imm(1),Chain_Length
  306. #ifdef UNALIGNED_OK
  307.     movew    IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
  308.     movew    IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  309. #else
  310.     moveb    IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
  311.     lslw    imm(8),Scan_Start
  312.     moveb    IndBase(-MIN_MATCH+1,Scan_Ini),Scan_Start
  313.     moveb    IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  314.     lslw    imm(8),Scan_End
  315.     moveb    IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
  316. #endif
  317.     bras    L__do_scan
  318.  
  319. L__long_loop:
  320. #ifdef UNALIGNED_OK
  321.     movew    IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  322. #else
  323.     moveb    IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  324.     lslw    imm(8),Scan_End
  325.     moveb    IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
  326. #endif
  327.  
  328. L__short_loop:
  329.     lslw    imm(1),Cur_Match
  330.     movew    IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match
  331.     cmpw    invert_maybe(Limit,Cur_Match)
  332.     dbls    Chain_Length,L__do_scan
  333.     bras    L__return
  334.  
  335. L__do_scan:
  336.     movel    Match_Ini,Match
  337.     addl    Cur_Match,Match
  338. #ifdef UNALIGNED_OK
  339.     cmpw    invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End)
  340.     bne    L__short_loop
  341.     cmpw    invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start)
  342.     bne    L__short_loop
  343. #else
  344.     moveb    IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_Test
  345.     lslw    imm(8),Scan_Test
  346.     moveb    IndBaseNdxw(-MIN_MATCH,Match,Best_Len),Scan_Test
  347.     cmpw    invert_maybe(Scan_Test,Scan_End)
  348.     bne    L__short_loop
  349.     moveb    IndBase(-MIN_MATCH,Match),Scan_Test
  350.     lslw    imm(8),Scan_Test
  351.     moveb    IndBase(-MIN_MATCH+1,Match),Scan_Test
  352.     cmpw    invert_maybe(Scan_Test,Scan_Start)
  353.     bne    L__short_loop
  354. #endif
  355.  
  356.     movew    imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter
  357.     movel    Scan_Ini,Scan
  358. L__scan_loop:
  359.     cmpmb    postinc(Match),postinc(Scan)
  360.     dbne    Loop_Counter,L__scan_loop
  361.  
  362.     subl    Scan_Ini,Scan
  363.     addql    imm(MIN_MATCH-1),Scan
  364.     cmpl    invert_maybe(Best_Len,Scan)
  365.     bls    L__short_loop
  366.     movel    Scan,Best_Len
  367.     movel    Cur_Match,_match_start
  368.     cmpl    invert_maybe(_nice_match,Best_Len)
  369.     blos    L__long_loop
  370. L__return:
  371.     moveml    postinc(Stack_Pointer),imm(popreg)
  372.     rts
  373.  
  374. #else
  375.  error: this asm version is for 386 or 680x0 only
  376. #endif /* mc68000 || mc68020 */
  377. #endif /* i386 || _I386   */
  378.